#include "mgraph.h"
#include <memory.h>
#include <list>

using std::cout;
using std::endl;
using std::list;

MGraph::MGraph(GraphKind gk)
{
	memset(this->vexs, 0, sizeof(this->vexs));
	memset(this->visited, 0, sizeof(this->visited));
	memset(this->arcs, 0, sizeof(this->arcs));
	this->Graphkind = gk;
	this->vexnum = this->arcnum = 0;
}

Status MGraph::CreateGraph()
{
	return OK;
}

Status MGraph::DestroyGraph()
{
	memset(this->vexs, 0, sizeof(this->vexs));
	memset(this->visited, 0, sizeof(this->visited));
	memset(this->arcs, 0, sizeof(this->arcs));
	this->vexnum = this->arcnum = 0;
	return OK;
}

int MGraph::LocateVex(VertexType u)
{
	for(int i = 0; i < this->vexnum; i++)
		if(this->vexs[i] == u)
			return i;
	return -1;									//没有找到该顶点
}

VertexType MGraph::GetVex(VertexType v)
{
	int i;
	for(i = 0; i < this->vexnum; i++)
		if(this->vexs[i] == v)
			return v;
	cout << "The vertex is not exist" << endl;
	return -1;
}

Status MGraph::PutVex(VertexType v, VertexType value)
{
	for(int i = 0; i < this->vexnum; i++)
		if(this->vexs[i] == v)
		{
			this->vexs[i] = value;
			return OK;
		}
	return ERROR;
}

VertexType MGraph::FirstAdjVex(VertexType v)
{
	int vexid = -1, i;
	for(i = 0; i < this->vexnum; i++)
		if(this->vexs[i] == v)
		{
			vexid = i;
			break;
		}
	if(vexid == -1)
	{
		cout << "The vertex is not exist" << endl;
		return -1;
	}
	for(i = 0; i < this->vexnum; i++)
		if(this->arcs[vexid][i].adj)
			return this->vexs[i];
	cout << "The adjacent vertex is not exist" << endl;
	return -1;
}

VertexType MGraph::NextAdjVex(VertexType v, VertexType w)
{
	int vexsId = -1, vexbId = -1;
	vexsId = this->LocateVex(v);
	vexbId = this->LocateVex(w);
	if(vexsId == -1 || vexbId == -1)
	{
		cout << "The vertex is not exist." << endl;
		return ERROR;
	}
	for(int i = vexbId+1; i < this->vexnum; i++)
		if(this->arcs[vexsId][i].adj)
			return this->vexs[i];
	cout << "The adjacent vertex is not exist" << endl;
	return -1;
}

Status MGraph::InsertVex(VertexType v)
{
	if(this->vexnum == MAX_VERTEX_NUM)
		return OVERFLOW;
	this->vexs[vexnum] = v;
	this->vexnum++;
	return OK;
}

Status MGraph::DeleteVex(VertexType v)
{
	int vexp;
	int i, j;
	vexp = this->LocateVex(v);
	if(vexp == -1)
	{
		cout << "The vertex is not exist." << endl;
		return ERROR;
	}
	for(i = vexp+1; i < this->vexnum; i++)
		this->vexs[i-1] = this->vexs[i];
	for(i = vexp+1; i < this->vexnum; i++)
		for(j = 0; j < this->vexnum; j++)
			this->arcs[i-1][j] = this->arcs[i][j];
	for(i = vexp+1; i < this->vexnum; i++)
		for(j = 0; j < this->vexnum; j++)
				this->arcs[j][i-1] = this->arcs[j][i];
	for(i = 0; i < this->vexnum; i++)
	{
		this->arcs[this->vexnum-1][i].adj = 0;
		this->arcs[i][this->vexnum-1].adj = 0;
	}
	this->vexnum--;
	return OK;
}

Status MGraph::InsertArc(VertexType v, VertexType w, int weight=1)
{
	int vexsId = -1, vexeId = -1;
	vexsId = this->LocateVex(v);
	vexeId = this->LocateVex(w);
	if(vexsId == -1 || vexeId == -1)
	{
		cout << "The vertex is not exist." << endl;
		return ERROR;
	}
	if(this->Graphkind == DG || this->Graphkind == UDG)
		this->arcs[vexsId][vexeId].adj = 1;
	else
		this->arcs[vexsId][vexeId].adj = weight;
	if(this->Graphkind == UDN || this->Graphkind == UDG)
		this->arcs[vexeId][vexsId].adj = this->arcs[vexsId][vexeId].adj;
	return OK;
}

Status MGraph::DeleteArc(VertexType v, VertexType w)
{
	int vexsId, vexeId;
	vexsId = this->LocateVex(v);
	vexeId = this->LocateVex(w);
	if(vexsId == -1 || vexeId == -1)
	{
		cout << "The vertex is not exist." << endl;
		return ERROR;
	}
	this->arcs[vexsId][vexeId].adj = 0;
	if(this->Graphkind == UDG || this->Graphkind == UDN)
		this->arcs[vexeId][vexsId].adj = 0;
	return OK;
}

Status MGraph::DFSTraverse(Status (*visit)(VertexType v), int startVex = 0, int f = 0)
{
	int SVId = this->LocateVex(startVex);
	if(SVId == -1)
	{
		cout << "The vertex is not exist." << endl;
		return ERROR;
	} 
	this->visited[SVId] = true;
	(*visit)(this->vexs[SVId]);
	for(int i = 1; i < this->vexnum; i++)
		if(this->arcs[SVId][i].adj && (!this->visited[i]))
			this->DFSTraverse(visit, i, f+1);
	if(f == 0)
		memset(this->visited, 0, sizeof(this->visited));
	return OK;
}

Status MGraph::BFSTraverse(Status (*visit)(VertexType v), int startVex = 0)
{
	list<int> queue;
	int cur, SVId = this->LocateVex(startVex);
	if(SVId == -1)
	{
		cout << "The vertex is not exist." << endl;
		return ERROR;
	}
	queue.push_back(this->vexs[SVId]);
	while(!queue.empty())
	{
		cur = queue.front();
		queue.pop_front();
		if(!this->visited[cur])
		{
			this->visited[cur] = true;
			(*visit)(this->vexs[cur]);
		}
		for(int i = 0; i < this->vexnum; i++)
			if(this->arcs[cur][i].adj && (!this->visited[i]))
				queue.push_back(i);
	}
	memset(this->visited, 0, sizeof(this->visited));
	return OK;
}
